﻿#define _CRT_SECURE_NO_WARNINGS 1
//给定⼀个⼆进制数组nums, 找到含有相同数量的0和1的最⻓连续⼦数组，并返回该⼦数组的⻓度。
//eg: 输⼊ : nums = [0, 1]  输出:2
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int findMaxLength(vector<int> nums)
{
	int n = nums.size();

	vector<int> arr(n);
	for (int i = 0; i < n; i++)
	{
		nums[i] == 0 ? arr[i] = -1 : arr[i] = 1;
	}

	unordered_map<int, int> hash;
	hash[0] = -1;//默认有一个前缀和为0的情况
	int sum = 0, ret = 0;
	for (int i = 0; i < n; i++)
	{
		sum += arr[i];//计算当前位置的前缀和
		if (hash[sum])
		{
			int max = i - hash[sum];
			if (max > ret)
			{
				ret = max;
			}
		}
		else
			hash[sum]=i;
	}

	return ret;
}

int main()
{
	vector<int> nums({ 0,1,1,1,0,0,1,1});
	int an = findMaxLength(nums);
	cout<<an<<endl;

	return 0;
}